Because of the wide-spread use of smart phones and seamless wireless network infrastructures, people are becoming familiar with acquiring information via mobile phones. Quick response (QR) code is proposed as an information container which can be captured and decoded by smart phones directly. QR code is a matrix bar code containing a much larger amount of information than its one dimensional (1D) counterpart. QR code has error correcting capabilities since Reed Solomon (RS) codes have already been integrated into the standard QR codes. With the aid of QR codes, users can avoid tedious typing on the small size screens of smart phones. Numerous applications are therefore built based on QR codes with various sizes, since QR codes provide a convenient way for mobile information acquisition.
FIG. 1a and FIG. 1b are views that illustrate that the conventional QR codes and the images are embedded together in the conventional QR codes. As shown in FIG. 1a and FIG. 1b, the appearance of QR code is designed for machine read only, which consists of meaningless noise-like patterns. The noise-like appearance of QR code will disturb the visual design, when the QR code is put into the host material, say a poster, directly. Since QR code is decoded on the basis of appearance, the design of QR code for producing a visually pleasant appearance while not affecting the accuracy of the decoded message becomes a major challenge. One of the common approaches enforced in QR design is embedding an icon directly. This approach introduces invalid codewords in the resultant QR code, where the changeable area is bounded by the error correction capability, that is, the maximum area is usually less than 30% of the whole QR code area (which is determined by the maximum error correction level of the QR code).
QR code is one of two-dimensional bar codes consisting of black and white square blocks where the smallest block (black or white) is defined as the module of a standard QR code. The codeword of a QR code consists of 8 bits, where one module represents the value of 1 bit (white for logical 0 and black for logical 1). The size of a QR code is determined by the version number V, where V≦40, which corresponds to the size of (17+4V)×(17+4V) modules.
FIG. 2 is a structural view of a conventional QR code. As shown in FIG. 2, the structure of the QR code 20 includes finder patterns 202. The finder patterns 202 are located at the three corners of the QR code 20. The finder pattern 202 is the most important pattern which enables the detection of the position of a QR code. Besides the finder patterns 202, there is timing pattern 204, version information 206, and formation information 208. For a QR code with version number V≧2, there will be alignment patterns 210 for correcting the warping effect. The alignment pattern 210 is for aligning a warping effect. The finder pattern 202, timing pattern 204, and alignment pattern 210 are called function patterns of a QR code. The other regions are defined as encoding regions which can be used to store the information and the error correction codewords.
QR code utilizes RS codes for providing error correcting capabilities where the codewords are represented by and appear in consecutive modules. There are four error correction levels (i.e. L, M, Q, and H from low to high) which can recover 7%, 15%, 25% and 30% of error codewords of the whole QR code. For example, a QR code with version number V=10 and the correction level L is denoted as (10, L)-QR code. Table 1 shows a list of the numbers of data codewords and error correction codewords for different QR code configurations with different error tolerance levels. The target of QR code beautification is to find the valid codewords that achieve a visually pleasing appearance within the search space. Table 1 has demonstrated the difficulty of QR code beautification because of the tremendous number of possible combinations.
Version, RecoveryNum. Num. of error CorrectionCapacity of datacorrectionlevel(%)codewordscodewords(15, L) 7 523 132(15, M)15 415 240(15, Q)25 295 360(15, H)30 223 432(35, L) 72306 570(35, M)1518121064(35, Q)2512861590(35, H)30 9861890
FIG. 3 illustrates a flowchart for generating a standard QR code, which includes the data analysis, the data encoding, the error correction encoding, and the placement and masking stages. In data analysis Stage S302, the information is analyzed in the data analysis stage S302 which determines the error correction level and the encoding mode (e.g. numeric, alphanumeric). The suitable version and the capacity of QR code are decided is this stage. In data encoding stage S304, the embedding information is encoded into a bit stream according to the associated encoding mode, the terminator symbols (0000) are added to the end of the bit stream and then the resultant bit stream is converted to 8-bit data codewords. If the number of codewords does not reach the capacity of the corresponding QR code, padding codewords are added. In error correction encoding stage S306, in order to resist the noise during QR code acquisition, RS code is integrated into the standard QR code. RS code is utilized to detect and correct noise induced errors. RS code is very useful for correcting burst errors and is one kind of [n, k] non-binary linear block code, where n denotes the length of the coding block and k represents the length of the message (i.e. the number of data codewords). The length of the parity codeword is n−k. RS code can correct up to t errors, where t is calculated as:
      t    =                  [                              n            -            k                    2                ]            -              equation        ⁢                                  ⁢                  (          1          )                      ,and [x] denotes the largest integer smaller than x.
The values of n and k are fixed in standard QR codes for a given version number and an error correction level. The errors are detected by checking the syndromes, denoted as S(x), which are calculated by multiplying the party-check matrix H with a given RS codeword, C(x), that is S(x)=H(x)·C(x) (equation (2)). The dimension of the parity check matrix H is (n−k)×n, and C(x) is an n×1 column vector. The verification process of legal RS codewords can be represented as:
                                                                 [                                                                    1                                                        1                                                        ⋯                                                        1                                                                                                              α                                              n                        -                        1                                                                                                                        α                                              n                        -                        2                                                                                                  ⋯                                                        1                                                                                        ⋮                                                        ⋮                                                        ⋱                                                        ⋮                                                                                                                                      (                                                  α                                                      n                            -                            k                            -                            1                                                                          )                                                                    n                        -                        1                                                                                                                                                (                                                  α                                                      n                            -                            k                            -                            1                                                                          )                                                                    n                        -                        2                                                                                                  ⋯                                                        1                                                              ]                        ⁡                          [                                                                                          C                      1                                                                                                                                  C                      2                                                                                                            ⋮                                                                                                              C                      n                                                                                  ]                                =                      [                                                            0                                                                              0                                                                              ⋮                                                                              0                                                      ]                                              equation        ⁢                                  ⁢                  (          3          )                    
where α is a primitive root in a finite field F, and both α and F are specified in the QR code as standard.
Within the QR code, there are three kinds of codewords (information, padding and parity) embedded in different regions of a QR code. In the masking stage, the masking operation is utilized to eliminate the situations that the appearance of the encoded codewords in the placement regions are identical to those of the function patterns.
Accordingly, the conventional beautifying method in the QR code is not good enough. A need has arisen to design a beautifying method for the QR code without reducing the identification efficiency of the QR code.